COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	(Assumes knowledge of WHILE)
C00010 ENDMK
C⊗;
(Assumes knowledge of WHILE)

I want a program to read a long list of numbers and add them, printing the
sum at the end. I could use the definite iteration ("FOR"), preceding the
list with a count of how many data there are.

INPUT:   3     2.1    3.5     4.2

PROGRAM: (Declarations and such)
	 READ (N)
	 SUM:= 0;
	 FOR I:= 1 TO N DO
		BEGIN
		READ (X)
		SUM:= SUM + X
		END
	 END.

OUTPUT:  9.8

There are two disadvantages:

     (1) The user must spend time counting the data, whether there are 
	 three or three thousand.

     (2) If the user counts wrongly, the program may omit some data at
	 the end, without any obvious symptom of error, or may try to
	 read more data than there are, resulting in an end-of-file error.

Instead, I follow the data with a special value I know will not occur among
the data. If the data are the amounts of the checks I have written this
month, 999999 will do fine:

INPUT:	2.1	3.5	4.2	999999.0

The 999999.0 has no quantitative meaning; it is called a _sentinel_.

I want an algorithm which initializes SUM to zero. It then repeatedly
reads, and as long as it reads a non-zero value, increases sum by that
value. For the input above, the sequence of computational operations
should be:

SUM:= 0
READ (X)   (X=2.1)
TEST X < BIG: TRUE
SUM:= SUM+X   (SUM=2.1)
READ (X)   (X=3.5)
TEST X < BIG: TRUE
SUM:= SUM+X   (SUM=5.6)
READ (X)   (X=4.2)
TEST X < BIG: TRUE
SUM:= SUM+X   (SUM=9.8)
READ (X)   (X=999999.0)
TEST X < BIG: FALSE
WRITE(SUM)    (Print 9.8)

where BIG is a constant like 900000.0.

Some of these operations must be repeated as many times as needed; the READ,
the test, and the addition to SUM must therefore be inside an iteration.
Other operations, like initializing SUM to zero and printing its final value,
are done once and must not be iterated. Since the indefinite iteration
("WHILE") starts with a test, the pattern of each repetition must be:

(TEST)
SUM:= SUM+X
READ (X)

followed by a final test which finds the X≥BIG.

Suppose there are n data to be added, followed by one sentinel to mark the
end. There must be n+1 reads to bring in all these numbers, including the
sentinel. Each must be tested, so there are n+1 tests. Only n of the data
need be added to SUM, though.

Since the form

	WHILE condition DO **

makes the test once more than it executes **, the relation between the number
of tests and the number of additions is right, but one extra READ is needed.
Furthermore, the first test whether X<BIG only makes sense if X has already
been read. I must have a READ(X) before the iteration, as well as one inside.
Putting these requirements together, I get the iteration

WHILE X<BIG DO
	BEGIN
	SUM:= SUM+X;
	READ (X)
	END

preceded by

SUM:= 0
READ (X)

and followed by

WRITE(SUM).

The whole program is:

PROGRAM P(INPUT);
CONST BIG = 900000.0;
VAR SUM, X; REAL;
BEGIN
SUM:= 0;
READ (X);
WHILE X<BIG DO
	BEGIN
	SUM:= SUM+X;
	READ (X)
	END;
WRITE(SUM)
END.

The above program exemplifies a common pattern, where the iteration obtains
a set of data values and the last one is treated specially as a sentinel.
The first data value must be obtained before the iteration is entered.
The body of the iteration processes one data value, then obtains the next
one. Because some steps are done n times, and some n+1 times, such iterations
are called n-and-a-halfs. There are other ways to write them, but most have
pitfalls. A potential error in this kind of problem is to forget that there
might be zero data (suppose the program above is part of a larger program for
balancing my bank account, I've made deposits but written no checks this
month, and I want to bring my account balance up to date). The program above, 
if there are no data, reads the sentinel into X before entering the iteration. 
In the iteration, X is initially 999999.0, the iteration is instantly terminated, 
SUM remains zero, and is printed. Many otherwise plausible solutions fail
when there are no data at all.